package com.zjsru.plan2023.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: CookLee
 * @Date: 2023/6/13
 * 数组中不等三元组的数目
 *
 * 输入：nums = [4,4,2,4,3]
 * 输出：3
 * 解释：下面列出的三元组均满足题目条件：
 * - (0, 2, 4) 因为 4 != 2 != 3
 * - (1, 2, 4) 因为 4 != 2 != 3
 * - (2, 3, 4) 因为 2 != 4 != 3
 * 共计 3 个三元组，返回 3 。
 * 注意 (2, 0, 4) 不是有效的三元组，因为 2 > 0 。
 *
 * 输入：nums = [1,1,1,1,1]
 * 输出：0
 * 解释：不存在满足条件的三元组，所以返回 0 。
 */
public class UnequalTriplets {
    
    
    /**
     * 模拟
     *
     * @param nums
     * @return int
     */
    public int unequalTriplets(int[] nums) {
        int count = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                for (int k = j + 1; k < length; k++) {
                    boolean b = this.helper(nums, i, j, k);
                    if (b) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
    
    /**
     * 三值判断助手类
     *
     * @param nums 全国矿工工会
     * @param i    我
     * @param j    j
     * @param k    k
     * @return boolean
     */
    private boolean helper(int[] nums ,int i, int j, int k) {
        if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k] ) {
            return true;
        }
        return false;
    }
    
    /**
     * 使用hash表, 总公式：t×v×(n−t−v)，考虑 枚举中间的元素来获得不重复的所有结果
     *
     * @param nums
     * @return int
     */
    public int unequalTriplets2(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.merge(num, 1, Integer::sum);
        }
        //先前遍历的元素总数目为 t
        int res = 0, len = nums.length,t = 0;
        for (Map.Entry<Integer,Integer> entry: count.entrySet()) {
            res += t * entry.getValue() * (len - t -entry.getValue());
            t += entry.getValue();
        }
        return res;
    }
    
    public static void main(String[] args) {
        
        UnequalTriplets unequalTriplets = new UnequalTriplets();
        int[] nums = new int[] {4, 4, 2, 4, 3};
        System.out.println(unequalTriplets.unequalTriplets2(nums));
    }
    
}
